现实生活中的网络拓扑，可以抽象成由节点（路由器）和边（路由器之间的链路）构成的有向连通图，链路的代价可以抽象成边的权函数，之所以称为“有向”图，是因为同一条链路（边）不同方向的代价（权值）可能不一样。

路由器的重要功能之一是转发决策，即为分组报文选择到达目的网络的最短路径。路由器通过专门的路由协议来计算最短路径，以路由器自身为起点，计算出到网络中其他路由器的最短路径，然后考虑各路由器直连网络情况确定到达各个网络的路径。

既然网络可以抽象成有向连通图，那么路由协议计算最短路径的方法，就可以抽象成在有向连通图中，以某一节点为起点，找出到其他节点的最短路径。事实上，有向连通图中的最短路径计算方法，在数学上早已经有多种成熟算法，OSPF协议中用到的Dijkstra算法和RIP协议中用到的距离向量算法，都是相当经典的最短路径算法。

本文将对Dijkstra算法进行系统的描述，给出一个简洁的证明，并示例OSPF协议如何描述网络拓扑、如何进行最短路径计算。